#include <stdlib.h>
#include <string.h>
#include "base.h"
#include "map2.h"

/// @brief 初始容量
static const uint32_t map_init_cap = 16;
/// @brief 容量扩展倍数
static const float map_enlarging_multiple = 2.0;
/// @brief 使用/容量 扩容最小值
static const float map_enlarging_min_percentage = 0.9;
/// @brief 每次扩容执行使用时间
static const long long map_enlarging_used_ms = 80;

static struct
{
    map_malloc_impl malloc_func;
    map_free_impl free_func;
} map_memctl = {
    .malloc_func = malloc,
    .free_func = free,
};

struct map_entry_st
{
    void *key;
    void *val;
    // 当前节点hash值
    uint32_t hash;
    // 发生hash冲突时,启用开链法
    struct map_entry_st *next;
};

/// @brief 内部函数 初始化 map_entry_t
/// @param key
/// @param value
/// @return
static inline map_entry_t *__map_entry_init(void *key, void *value)
{
    map_entry_t *ptr = NULL;
    ptr = map_memctl.malloc_func(1 * sizeof(map_entry_t));
    if (ptr == NULL)
        goto fail0;
    ptr->key = key;
    ptr->val = value;
fail0:
    return ptr;
}

/// @brief 内部函数 释放 map_entry_t
/// @param entry
static inline void __map_entry_deinit(map_entry_t *entry)
{
    if (entry != NULL)
        map_memctl.free_func(entry);
}

/// @brief 内部函数 尝试扩容
/// @param map
/// @param ms 本次扩容允许用时
/// @return 插入数据使用的桶的下标
static inline char __map_try_enlarging(map_t *map, long long ms)
{

    char ret = 0;
    if (map->used >= map->cap * map_enlarging_min_percentage || map->rfidx > 0) // 需要扩容 或 已经在扩容阶段
        ret = 1;

    if (ret == 0) // 没达到扩容条件
        goto fail0;
    // 扩容状态
    long long start = now_ms();
    uint32_t new_cap = map->cap * map_enlarging_multiple;

    // 初始化1号桶
    if (map->entrys[1] == NULL)
    {
        map->entrys[1] = (map_entry_t **)map_memctl.malloc_func(new_cap * sizeof(map_entry_t *));
        if ((map->entrys[1]) != NULL)
            memset(map->entrys[1], 0, (new_cap * sizeof(map_entry_t *)));
        else // 无法申请空间
        {
            ret = 0; // 设置使用0号桶
            goto fail0;
        }
    }

    // 遍历0号桶所有链
    for (size_t i = map->rfidx; i < map->cap; i++)
    {
        map_entry_t *entry = map->entrys[0][i];
        // 转移0号桶数据到1号桶
        map_entry_t *next_entry = NULL;
        // 链遍历
        while (entry != NULL)
        {
            // 暂存旧数据->next
            next_entry = entry->next;

            // 摘除0号桶链表的本次节点
            if (map->entrys[0][i] == entry)
                map->entrys[0][i] = next_entry;

            // 转移数据到1号桶
            map_entry_t *new_e = entry;
            uint32_t idx = entry->hash % new_cap;
            new_e->next = (map->entrys[1][idx]);
            map->entrys[1][idx] = new_e;

            entry = next_entry;
        }
        map->rfidx++;

        // 扩容完毕 =>化1号桶为0号桶
        if (map->rfidx == map->cap)
        {
            // 释放0号桶容器，里面的元素已经被转移到1号桶了
            map_memctl.free_func(map->entrys[0]);
            map->entrys[0] = map->entrys[1];
            map->entrys[1] = NULL; // 置空1号桶
            map->cap = new_cap;
            map->rfidx = 0; // 扩容进度回滚
            ret = 0;
            goto fail0;
        }

        long long use_ms = now_ms() - start;

        // 处理完一条链后判断超时=>退出
        if (use_ms >= ms)
            goto fail0;
    }

fail0:
    return ret;
}

/// @brief map内存控制函数设置
/// @param map_malloc_func 申请内存函数
/// @param map_free_func 释放内存函数
void map_memctl_set(map_malloc_impl map_malloc_func, map_free_impl map_free_func)
{
    map_memctl.malloc_func = map_malloc_func;
    map_memctl.free_func = map_free_func;
}

/// @brief 外部函数 初始化map
/// @param map map_t 变量地址
/// @param hash_fn 指定hash函数
/// @param equal_fn 指定equal函数
/// @param deinit_before_fn deinit map桶内元素释放函数
void map_init(map_t *map, map_hash_impl hash_fn, map_equal_impl equal_fn, map_deinit_before_impl deinit_before_fn)
{
    if (hash_fn == NULL || equal_fn == NULL)
        return;
    map->hash_fn = hash_fn;
    map->equal_fn = equal_fn;
    map->deinit_before_fn = deinit_before_fn;
    map->used = 0;
    map->cap = map_init_cap;
    map->rfidx = 0;
    // 数据容器初始化
    for (size_t i = 0; i < 2; i++)
    {
        if (i == 0)
        {
            map->entrys[i] = (map_entry_t **)map_memctl.malloc_func(map->cap * sizeof(map_entry_t *));
            if ((map->entrys[i]) != NULL)
                memset(map->entrys[i], 0, (map->cap * sizeof(map_entry_t *)));
        }
        else
        {
            map->entrys[i] = NULL;
        }
    }
}

/// @brief 外部函数 初始化map 允许定义hashtable容量
/// @param map map_t 变量地址
/// @param cap 容器容量 容量
/// @param hash_fn 指定hash函数
/// @param equal_fn 指定equal函数
/// @param deinit_before_fn deinit map桶内元素释放函数
void map_init1(map_t *map, uint32_t cap, map_hash_impl hash_fn, map_equal_impl equal_fn, map_deinit_before_impl deinit_before_fn)
{
    if (hash_fn == NULL || equal_fn == NULL)
        return;
    map->hash_fn = hash_fn;
    map->equal_fn = equal_fn;
    map->deinit_before_fn = deinit_before_fn;
    map->used = 0;
    map->cap = cap;
    map->rfidx = 0;
    // 数据容器初始化
    for (size_t i = 0; i < 2; i++)
    {
        if (i == 0)
        {
            map->entrys[i] = (map_entry_t **)map_memctl.malloc_func(map->cap * sizeof(map_entry_t *));
            if ((map->entrys[i]) != NULL)
                memset(map->entrys[i], 0, (map->cap * sizeof(map_entry_t *)));
        }
        else
        {
            map->entrys[i] = NULL;
        }
    }
}

/// @brief 外部函数 释放map
/// @param map map_t 变量地址
void map_deinit(map_t *map)
{
    if (map == NULL)
        return;
    // 在扩容中 len = 2;
    char len = map->rfidx == 0 ? 1 : 2;
    for (char i = 0; i < len; i++)
    {
        uint32_t cap = i == 0 ? map->cap : map->cap * map_enlarging_multiple;
        for (size_t j = 0; j < cap; j++)
        {
            map_entry_t *e = (map->entrys[i][j]);
            map_entry_t *next = (map->entrys[i][j]);
            while (e)
            {
                next = e->next;
                if (map->deinit_before_fn != NULL)
                    map->deinit_before_fn(e->key, e->val);
                __map_entry_deinit(e);
                map->used--;
                e = next;
            }
        }
        map_memctl.free_func(map->entrys[i]);
        map->entrys[i] = NULL;
    }
    map->hash_fn = NULL;
    map->equal_fn = NULL;
    map->deinit_before_fn = NULL;
    map->cap = 0;
    map->rfidx = 0;
}

/// @brief 外部函数 往map中放入键值对
/// @param map map_t 变量地址
/// @param key 地址
/// @param keylen key变量真实长度
/// @param value 地址
/// @return 成功:0 失败:-1=> 参数错误 -2=> 内存不足 1=> 已经存在该key
int8_t map_put(map_t *map, void *key, uint32_t keylen, void *value)
{
    if (map == NULL || map->hash_fn == NULL || map->equal_fn == NULL)
        return -1;
    char eidx = __map_try_enlarging(map, map_enlarging_used_ms);
    char len = eidx == 1 ? 2 : 1;
    uint32_t hash = map->hash_fn(key, keylen);
    for (char i = 0; i < len; i++)
    {
        uint32_t cap = i == 0 ? map->cap : map->cap * map_enlarging_multiple;
        uint32_t idx = hash % cap;
        map_entry_t *e = (map->entrys[i][idx]);
        while (e != NULL)
        {
            int equal_ret = map->equal_fn(e->key, key);
            if (equal_ret == 1)
                return 1;
            e = e->next;
        }
        // 不在扩容阶段 或者 扩容时遍历到1号桶
        if (len == 1 || i == 1)
        {
            map_entry_t *new_e = __map_entry_init(key, value);
            if (new_e == NULL)
                return -2;
            new_e->hash = hash;
            new_e->next = (map->entrys[i][idx]);
            map->entrys[i][idx] = new_e;
            map->used++;
        }
    }
    return 0;
}
/// @brief 外部函数 更新map中键值对
/// @param map map_t 变量地址
/// @param key 键
/// @param keylen 键长度
/// @param value 值
/// @return 成功:0 失败:-1=> 参数错误 -2=> 不存在该key
int8_t map_upt(map_t *map, void *key, uint32_t keylen, void *value)
{
    if (map == NULL || map->hash_fn == NULL || map->equal_fn == NULL)
        return -1;
    char eidx = __map_try_enlarging(map, map_enlarging_used_ms);
    char len = eidx == 1 ? 2 : 1;
    uint32_t hash = map->hash_fn(key, keylen);
    for (char i = 0; i < len; i++)
    {
        uint32_t cap = i == 0 ? map->cap : map->cap * map_enlarging_multiple;
        uint32_t idx = hash % cap;
        map_entry_t *e = (map->entrys[i][idx]);
        while (e != NULL)
        {
            int equal_ret = map->equal_fn(e->key, key);
            if (equal_ret == 1)
            {
                e->val = value;
                return 0;
            }
            e = e->next;
        }
    }
    return -2;
}

/// @brief 外部函数 获取map中键对应的值
/// @param map map_t 变量地址
/// @param key
/// @param keylen
/// @return 存在返回void *变量;失败返回NULL
void *map_get(map_t *map, void *key, uint32_t keylen)
{
    if (map == NULL || map->hash_fn == NULL || map->equal_fn == NULL)
        return NULL;
    uint32_t hash = map->hash_fn(key, keylen);
    char eidx = __map_try_enlarging(map, map_enlarging_used_ms);
    char len = eidx == 1 ? 2 : 1;
    for (char i = 0; i < len; i++)
    {
        uint32_t cap = i == 0 ? map->cap : map->cap * map_enlarging_multiple;
        uint32_t idx = hash % cap;
        map_entry_t *e = (map->entrys[i][idx]);
        while (e != NULL)
        {
            int equal_ret = map->equal_fn(e->key, key);
            if (equal_ret == 1)
                return e->val;
            e = e->next;
        }
    }
    return NULL;
}

/// @brief 外部函数 删除map中指定键值对
/// @param map map_t 变量地址
/// @param key
/// @param keylen 成功:0 失败:-1=>参数异常 1:没找到指定key
/// @return
int8_t map_del(map_t *map, void *key, uint32_t keylen)
{
    if (map == NULL || map->hash_fn == NULL || map->equal_fn == NULL)
        return -1;
    uint32_t hash = map->hash_fn(key, keylen);
    char eidx = __map_try_enlarging(map, map_enlarging_used_ms);
    char len = eidx == 1 ? 2 : 1;
    for (char i = 0; i < len; i++)
    {
        uint32_t cap = i == 0 ? map->cap : map->cap * map_enlarging_multiple;
        uint32_t idx = hash % cap;
        map_entry_t **prev = &(map->entrys[i][idx]);
        map_entry_t *e = (map->entrys[i][idx]);
        while (e != NULL)
        {
            if (map->equal_fn(e->key, key))
            {
                *prev = e->next;
                __map_entry_deinit(e);
                map->used--;
                return 0;
            }
            *prev = e;
            e = e->next;
        }
    }
    return 1;
}

/// @brief 外部函数 遍历map
/// @param map map_t 变量地址
/// @param foreach_fn foreach函数 指定返回值为-1时跳出循环
/// @param userdata 用户自定义数据地址
/// @return 返回foreach函数累加数据
int64_t map_foreach(map_t *map, map_foreach_impl foreach_fn, void *userdata)
{
    if (map == NULL || foreach_fn == NULL)
        return -1;
    int64_t sum = 0;
    char eidx = __map_try_enlarging(map, map_enlarging_used_ms);
    char len = eidx == 1 ? 2 : 1;
    for (char i = 0; i < len; i++)
    {
        uint32_t cap = i == 0 ? map->cap : map->cap * map_enlarging_multiple;
        for (size_t j = 0; j < cap; j++)
        {
            map_entry_t *e = (map->entrys[i][j]);
            map_entry_t *next = (map->entrys[i][j]);
            while (e)
            {
                next = e->next;
                int foreach_ret = foreach_fn((const void *)e->key, e->val, userdata);
                if (foreach_ret == -1)
                    goto fail0;
                sum += foreach_ret;
                e = next;
            }
        }
    }
fail0:
    return sum;
}

/// @brief 外部函数 map使用情况
/// @param map map_t 变量地址
void map_used(map_t *map)
{
    if (map == NULL)
        return;
    printf("======map %p======\n", map);
    printf("cap:%u used:%u rfidx:%u\n", map->cap, map->used, map->rfidx);
    char len = map->rfidx == 0 ? 1 : 2;
    for (char i = 0; i < len; i++)
    {
        size_t cap = i == 0 ? map->cap : map->cap * map_enlarging_multiple;
        size_t list_count = 0;
        size_t e_count = 0;
        for (size_t j = 0; j < cap; j++)
        {
            map_entry_t *e = (map->entrys[i][j]);
            if (e != NULL)
                list_count++;
            while (e != NULL)
            {
                e_count++;
                e = e->next;
            }
        }
        printf("entry[%d] cap:%lu list_count:%lu e_count:%lu\n", i, cap, list_count, e_count);
    }
    printf("cap:%u used:%u rfidx:%u\n", map->cap, map->used, map->rfidx);
    printf("============\n");
}

/// @brief 外部函数 map执行 尝试扩容
/// @param map map_t 变量地址
/// @param count 执行次数
/// @return 最后一次 尝试扩容的返回值(0:扩容完成 1:扩容未完成)
char map_enlarging_forced(map_t *map, size_t count)
{
    char ridx = 0;
    size_t try_count = 0;
    count = count <= 0 ? 1 : count;
    do
    {
        ridx = __map_try_enlarging(map, map_enlarging_used_ms);
        printf("====== %d rfidx:%u\n", ridx, map->rfidx);
        count++;
    } while (ridx || try_count == count);
    return ridx;
}
/// @brief 外部函数 map执行 尝试扩容
/// @param map map_t 变量地址
/// @param ms 允许执行时间
/// @return 尝试扩容返回值(0:扩容完成 1:扩容未完成)
char map_enlarging_forced2(map_t *map, long long ms)
{
    return __map_try_enlarging(map, ms <= 0 ? map_enlarging_used_ms : ms);
}